class Solution {
public:
    int _m, _n, _cnt, sum;
    bool visit[100][100];
    int wardrobeFinishing(int m, int n, int cnt) {
        _m = m, _n = n;
        _cnt = cnt;
        sum++;
        visit[0][0] = true;
        dfs(0, 0);
        return sum;
    }
    int row[2] = { 0,1 };
    int col[2] = { 1,0 };
    void dfs(int r, int c)
    {
        for (int i = 0;i < 2;i++)
        {
            int x = r + row[i], y = c + col[i];
            if (x < _m && y < _n && !visit[x][y] && inspect(x, y, _cnt))
            {

                sum++;
                visit[x][y] = true;
                dfs(x, y);
            }
        }
    }
    bool inspect(int r, int c, int target)
    {
        int sum = 0;
        for (int i = 0;i < 3;i++)
        {
            sum += r % 10;
            sum += c % 10;
            r /= 10;
            c /= 10;
        }
        return sum <= target;
    }
};